package org.laizili.solution.leetcode;

import org.laizili.structure.tree.bitree.TreeNode;

/**
 * <a href="https://leetcode.cn/problems/delete-node-in-a-bst/">450. 删除二叉树中的结点</a>
 * <p>
 * tags: BST(二叉搜索树)性质; 递归
 */
public class Problem450 {
    private static class Solution {
        public TreeNode deleteNode(TreeNode root, int key) {
            //find and delete
            if (root == null) {
                return null;
            }
            if (root.val == key) {
                if (root.right == null) {
                    root = root.left;
                } else {
                    // find the most left node of root.right, and make this node as new root
                    TreeNode prev = root;
                    TreeNode curr = root.right;
                    while (curr.left != null) {
                        prev = curr;
                        curr = curr.left;
                    }
                    if (prev == root) {
                        root = curr;
                        root.left = prev.left;
                    } else {
                        prev.left = curr.right;
                        curr.right = root.right;
                        curr.left = root.left;
                        root = curr;
                    }
                }
            } else if (key < root.val) {
                root.left = deleteNode(root.left, key);
            } else {
                root.right = deleteNode(root.right, key);
            }

            return root;
        }
    }
}
